import java.util.*;
public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
    public int[] productExceptSelf(int[] nums) {
        int n=nums.length;
        int[] answer=new int[n];
        answer[0]=1;
        for(int i=1;i<n;i++){
            answer[i]=answer[i-1]*nums[i-1];
        }
        int sum=1;
        for(int i=n-1;i>=0;i--){
            answer[i]*=sum;
            sum*=nums[i];
        }
        return answer;
    }
    public int pivotIndex(int[] nums) {
        int n=nums.length;
        int[] f=new int[n];//前缀和
        int[] g=new int[n];//后缀和
        f[0]=0;
        g[n-1]=0;
        for(int i=1;i<n;i++){
            f[i]=f[i-1]+nums[i-1];
        }
        for(int i=n-2;i>=0;i--){
            g[i]=g[i+1]+nums[i+1];
        }
        for(int i=0;i<n;i++){
            if(f[i]==g[i]){
                return i;
            }
        }
        return -1;
    }
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> hash=new HashMap<>();
        hash.put(0,1);
        int n=nums.length;
        int sum=0,ret=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
            if(hash.containsKey(sum-k)){
                ret+=hash.get(sum-k);
            }
            hash.put(sum,hash.getOrDefault(sum,0)+1);
        }
        return ret;
    }
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer,Integer> hash=new HashMap<>();
        int n=nums.length;
        int sum=0,ret=0;
        hash.put(0,1);
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
            int modulus=(sum%k+k)%k;
            if(hash.containsKey(modulus)){
                ret+=hash.get(modulus);
            }
            hash.put(modulus,hash.getOrDefault(modulus,0)+1);
        }
        return ret;
    }
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int n=mat.length,m=mat[0].length;
        int[][] dp=new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mat[i-1][j-1];
            }
        }
        int[][] ret=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                int x1=Math.max(0,i-k);
                int y1=Math.max(0,j-k);
                int x2=Math.min(n-1,i+k);
                int y2=Math.min(m-1,j+k);
                ret[i][j]=dp[x2+1][y2+1]-dp[x1][y2+1]-dp[x2+1][y1]+dp[x1][y1];
            }
        }
        return ret;
    }
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] nums3=new int[nums1.length+nums2.length];
        int k=0,i=0,j=0;
        while(i<nums1.length&&j<nums2.length){
            if(nums1[i]>nums2[j]){
                nums3[k++]=nums2[j++];
            }
            else{
                nums3[k++]=nums1[i++];
            }
        }
        if(i>=nums1.length){
            while(j<nums2.length){
                nums3[k++]=nums2[j++];
            }
        }
        if(j>=nums2.length){
            while(i<nums1.length){
                nums3[k++]=nums1[i++];
            }
        }
        if(nums3.length%2!=0){
            return (double)nums3[nums3.length/2];
        }
        double mid=(nums3[nums3.length/2]+nums3[nums3.length/2-1])/2.0;
        return mid;
    }
}